package core;

public class BST<E extends Comparable<E>> {

	private E data;
	private BST<E> parent, left, right;

	
	public BST() { }
	
	public BST(E data) {
		this.data = data;
	}

	public void insert(BST<E> z) {
		BST<E> y = null;
		BST<E> x = this; // root
		
		// inserting root
		if (x.data == null) {
			x.data = z.data;
			z = this;
			return;
		}

		while (x != null) {
			y = x;
			
			if (z.data.compareTo(x.data) == 0){ // don't allow duplicate keys
				return;
			} else if (z.data.compareTo(x.data) < 0) {
				x = x.left;
			} else {
				x = x.right;
			}
		}

		z.setParent(y);

		if (z.data.compareTo(y.data) < 0) {
			y.setLeft(z);
		} else {
			y.setRight(z);
		}
	}
	
	public BST<E> search(E data){
		BST<E> x = this;
		while(x != null && x.data != null){
			if (x.data.compareTo(data) == 0){
				return x;
			} else if (x.data.compareTo(data) > 0) {
				x = x.left;
			} else {
				x = x.right;
			}
		}
		return null;
	}
	
	public BST<E> findNextLargest(E data){
		BST<E> x = this, y = null;
		while(x != null && x.data != null){
			if(data.compareTo(x.data) < 0){
				y = x;
				x = x.left;
			} else {
				x = x.right;
			}
		}
		return y;
	}
	
	public void printInOrder(BST<E> tree){
		if(tree != null){
			printInOrder(tree.left);
			System.out.print(tree + " ");
			printInOrder(tree.right);
		}
	}

	public void printPostOrder(BST<E> tree){
		if(tree != null){
			printInOrder(tree.left);
			printInOrder(tree.right);
			System.out.print(tree + " ");
		}
	}
	
	public void printPreOrder(BST<E> tree){
		if(tree != null){
			System.out.print(tree + " ");
			printInOrder(tree.left);
			printInOrder(tree.right);
		}
	}
	public E getData() {
		return data;
	}

	public void setData(E data) {
		this.data = data;
	}

	public BST<E> getParent() {
		return parent;
	}

	public void setParent(BST<E> parent) {
		this.parent = parent;
	}

	public BST<E> getLeft() {
		return left;
	}

	public void setLeft(BST<E> left) {
		this.left = left;
	}

	public BST<E> getRight() {
		return right;
	}

	public void setRight(BST<E> right) {
		this.right = right;
	}
	
	@Override
	public String toString() {
		return data.toString();
	}

}
